#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <limits>
#include <algorithm>
#include <sstream>
#include <deque>
#include <list>


using namespace std;

#define CALLES_MAX 60
#define VERTICES_MAX 400
#define MAX_GRADO 1000
#define CANT_MOTOQUEROS 4
#define CANT_ROLLISTAS 2
#define INFINITY 1000
#define RADIO_ROLLISTAS 4
#define CAPACIDAD_ROLLISTAS 3
#define CAPACIDAD_MOTOQUEROS 8
#define MATRIZ_ROLLISTAS 1
#define MATRIZ_MOTOQUEROS 2
#define MOTOQUERO 1
#define ROLLISTA 2

/*************************************************/
/* UTN FRSF DISI - ProgramaciÃ³n Competitiva 2013 */
/*           Trabajo PrÃ¡ctico Nro 2              */
/*        Baragiola - Bonet - Cabrera            */
/*************************************************/

/**
* Estructuras
**/

struct Vertice
	{
		vector<int> calle;
		vector<int> altura;
	};

struct Segmento
	{
		int v; // nodo vecino
		int weight; // peso, por ahora ignorado
	};

struct Direccion
	{
		string calle;
		int altura;
	};

struct Repartidor {
	vector < vector <int> > recorridos; // vertices de cada recorrido
	int cantidadCuadras;
	
	bool disponible; //estado: true disponible, false ocupado
	vector<Direccion> historialPedidos;
};

struct InfoAdyacencia{
	int distancia;
	int padre;
	
};

struct Grafo
	{
		vector<vector<InfoAdyacencia> > infoAdy;   // informacion de distancias y recorridos
		vector<vector<InfoAdyacencia> > infoAdyRollista; 
		vector<vector<Segmento> > segmentos;   // segmentos del grafo
		
		int nsegmentos_unicos;
		int nsegmentos_dobles;
		int ncalles;                           
		int nvertices;                                 
		
		vector<bool> processed;
		vector<bool> discovered;
		vector<int> parents;  // se utiliza para imprimir alguna solucion de la busqueda
		vector<int> distance; // distancia optima al inicio despues de aplicar dijkstra 
		bool finished;       // se utiliza como corte de la busqueda en profundidad
		
		map<string, int> calles;
		vector<Vertice> vertices;
		vector<int> verticesUsados;
		vector<int> verticesEnRadio;
	};

struct Pizzeria {
	
	Direccion dir;
	vector<Direccion> pedidos;
	vector<Repartidor> repartidoresR;
	vector<Repartidor> repartidoresM;
	
	int verticePizzeria;
};


multimap<unsigned,unsigned> graf_aux,graf_aux2;
map<unsigned,unsigned> vertices,vertices2;
int cont, vert;
int totalCuadrasEnunciado, totalCuadrasMejora;

void menu();
int getCantPtosArticulacion();
int getNivelConectividad();
void read2();
void reread();
int connected_components(Grafo g);
void inicializarMatrizMotoqueros();
void inicializarMatrizRollistas();
void incisoA();
void leerCalles();
void imprimirCalles();
void read();
void leerVertices();
void imprimirVertices();
void leerSegmentos();
void leerPedidos();
void leerPedidosVIP();
void leerUbicacionPizzeria();
void dijkstra(int start);
void calcularDistanciasRollistas();
void calcularDistanciasMotoqueros();
void prim(int start);
void print();
void print_path(int dest);  
void print_parents();
void crearRepartidores();
int obtenerEsquina(Direccion pedido, bool dirigido);
void procesarPedidos();
void procesarPedidosMejora();
int* procesarPedidoVIP(Direccion &pedido);
bool compararDireccionesR(Direccion d1, Direccion d2);
bool compararDireccionesM(Direccion d1, Direccion d2);
int siguienteVertice(int v);
vector<int> obtenerCamino(int v1, int v2, int);
int obtenerDistanciaM(int v1, int v2);
int obtenerDistanciaR(int v1, int v2);
int sumaFloyd(int x, int y);
bool bfs(int start, int borrado);
void verticesRadio(int centro);
bool hayMotoqueros();
bool hayRollistas();
int obtenerRollista();
int obtenerMotoquero();
Direccion direccionMasLejana(Direccion, vector<Direccion> &, int);
Direccion direccionMasCercana(Direccion, vector<Direccion> &, int);
bool pertenece(vector<int> &vector, int elem);
void mostrarRecorrido(vector<int>);
void mostrarInforme(int &);
void mostrarInformeFinal();
void resetearContadores();
void verticesIncluidosEnRadios(int, int, int, vector<int> &);
vector<Direccion> elegirDirecciones(int, int, vector<Direccion> &, int);
vector<int> obtenerVerticesEntrega(vector<Direccion>);
void procesarRollista(int, Direccion);
void quitarDireccion(Direccion, vector<Direccion> &);
void liberarRepartidores();

Grafo g;
Pizzeria pizzeria;

Grafo g1, g2;
Segmento seg;

int main()
{
	totalCuadrasEnunciado = 0;
	totalCuadrasMejora = 0;
	
	leerCalles();
	
	read();
	
	calcularDistanciasMotoqueros(); //calcula las distancias de todos los vertices a todos los vertices
	
	leerUbicacionPizzeria();
	
	verticesRadio(pizzeria.verticePizzeria); //marca los vertices y segmentos que estan en el radio del rollista
	
	calcularDistanciasRollistas();
	crearRepartidores();
	
	menu();
	
	return 0;
}

void menu()
{
	int opcion = -1;
	while (opcion != 0)
	{
		cout << ":: MENU ::" << endl;
		cout << "1) Mostrar resumen del grafo (inciso A)." << endl;
		cout << "2) Procesar pedidos de manera solicitada en el enunciado." << endl;
		cout << "3) Procesar pedidos con la mejora desarrollada por el grupo." << endl;
		cout << "4) Comenzar a tomar pedidos VIP." << endl;
		cout << "5) Mostrar informe final." << endl;
		cout << "\n0) #MeQuieroIr" << endl;             
		
		cin >> opcion;
		switch (opcion)
		{
		case 0:
			break;
		case 1:
			incisoA();
			break;
		case 2:
			resetearContadores();
			leerPedidos();
			procesarPedidos();
			mostrarInforme(totalCuadrasEnunciado);
			break;
		case 3:
			resetearContadores();
			leerPedidos();
			procesarPedidosMejora();
			mostrarInforme(totalCuadrasMejora);
			break;
		case 4:
			leerPedidosVIP();
			break;
		case 5:
			mostrarInformeFinal();
			break;
		default:
			cerr << "Entrada errÃ³nea." << endl;
			break;
		}               
	}
}


int getCantPtosArticulacion(){
	
	int contador = 0;
	int verticeEliminado;
	//saca el primer elemento del vector verticesUsados realiza el recorrido bfs y luego lo inserta al final, asi hasta recorrer todo el vector
	for(int i =0; i< g.verticesUsados.size(); i++){
		
		//saca el vertice
		verticeEliminado = g.verticesUsados.front();
		g.verticesUsados.erase(g.verticesUsados.begin());
		
		
		
		bool aislado = bfs(g.verticesUsados.front(), verticeEliminado);
		
		if(aislado)
			contador++;
		
		
		
		//vuelve a agregar el verticeEliminado
		g.verticesUsados.push_back(verticeEliminado);
		
	}
	
	
	return contador;
}


int getNivelConectividad(){
	
	deque<unsigned> aux;
	unsigned arista_aux,x;
	int comp_con;
	
	cont = 0;
	
	read2();
	
	for (unsigned i = 0; i < g1.segmentos.size(); i++){
		if (!g1.segmentos[i].empty()){
			vertices.insert(make_pair(i,cont++));
			vertices2.insert(make_pair(cont-1,i));
			for (unsigned j=0; j < g1.segmentos[i].size(); j++){
				seg = g1.segmentos[i][j];
				graf_aux.insert(make_pair(i,seg.v));
			}
		}
	}
	
	
	multimap<unsigned,unsigned>::iterator it1;
	
	for (it1 = graf_aux.begin(); it1 !=graf_aux.end(); it1++)
		graf_aux2.insert(make_pair(vertices[(*it1).first],vertices[(*it1).second]));
	
	vert = vertices.size();
	reread();
	
	for (unsigned i=0; i < g2.segmentos.size(); i++) {
		for (unsigned j=0; j < g2.segmentos[i].size(); j++){
			seg = g2.segmentos[i][j];
			aux.push_back(seg.v);
		}
		x = g2.segmentos[i].size();
		g2.segmentos[i].clear();
		for (unsigned j=0; j < x; j++){
			arista_aux = aux.front();
			aux.pop_front();
			for (unsigned k=0; k < aux.size(); k++) {
				seg.v = aux[k];
				g2.segmentos[i].push_back(seg);
			}
			comp_con = connected_components(g2);
			seg.v = arista_aux;
			g2.segmentos[i].push_back(seg);
			aux.push_back(arista_aux);
			if (comp_con != 3){
				aux.clear();
				return 1;
			}
			g2.segmentos[i].clear();
		}
		aux.clear();

	}
	
	
	unsigned min_grado = MAX_GRADO;
	unsigned grado = 0;
	for (unsigned i=0; i < g2.segmentos.size(); i++) {
		
		grado = g2.segmentos[i].size();
		
		for (unsigned m = 0; m < g2.segmentos.size(); m++) 
			for (unsigned n = 0; n < g2.segmentos[m].size(); n++) {
				seg = g2.segmentos[m][n];
				if (seg.v == i) 
					grado++;
			}
		
		if (grado < min_grado)
				min_grado = grado;
	} 
	
	return min_grado;
}


void read2(){
	g1.nsegmentos_unicos = 0; 
	g1.segmentos.clear();
	Segmento seg_aux;
	
	
	g1.segmentos.resize(g.verticesUsados.size());   
	
	for(int i = 0; i < g.verticesUsados.size(); i++) {
		for( int j = 0; j < g.segmentos[g.verticesUsados[i]].size(); j++){
			
			seg_aux = g.segmentos[g.verticesUsados[i]][j];
			seg_aux.v--;
			g1.segmentos[i].push_back(seg_aux); 
			++g1.nsegmentos_unicos;
		}
		
	}
}       

void reread(){
	// initialize graph
	g2.nsegmentos_unicos = 0; 
	g2.segmentos.clear();
	
	g2.segmentos.resize(vert-1);    
	multimap<unsigned,unsigned>:: iterator it;
	for(it = graf_aux2.begin(); it != graf_aux2.end(); it++) {
		seg.v = (*it).second;
		g2.segmentos[(*it).first].push_back(seg); 
		++g2.nsegmentos_unicos;
		
	}               
}


int connected_components(Grafo g){
	int connected_count = 0;
	
	g.discovered.assign(g.segmentos.size(), false);
	
	for(unsigned i = 0; i < g.discovered.size(); i++){
		if(g.discovered[i]) continue;
		
		connected_count++;
		// BFS
		queue<int> q;
		q.push(i); 
		g.discovered[i] = true;                 // marcar como descubierto
		
		while (!q.empty()) {                    // mientras la cola no este vacia
			int v = q.front();              // obtener un elemento de la cola
			q.pop();
			
			for (unsigned i = 0; i < g.segmentos[v].size(); i++) {
				seg = g.segmentos[v][i];
				if(!g.discovered[seg.v]) {
					q.push(seg.v);
					g.discovered[seg.v] = true;
				}
			}
		}
		// end BFS
	}
	return connected_count;
}

void incisoA()
{
	cout << "\n\nINCISO A: " << endl;
	cout << "- Cantidad de calles: " << g.ncalles << endl;
	cout << "- Cantidad de vertices: " << g.nvertices << endl;
	cout << "- Cantidad de arcos de sentido unico: " << g.nsegmentos_unicos << endl;
	cout << "- Cantidad de arcos de sentido doble: " << g.nsegmentos_dobles << endl;
	cout << "- Cantidad de puntos de articulacion: " << getCantPtosArticulacion() << endl;
	cout << "- Nivel de conectividad por arcos: " << getNivelConectividad() << endl;
}

/**
* Lee las calles de 'calles.txt' y las
* carga en el vector calles.
*/
void leerCalles()
{
	ifstream archivo ("calles.txt");
	
	int nro;
	string nombre;
	g.ncalles = 0;
	g.calles.clear();
	
	if (archivo.is_open())
	{
		while (archivo.good() && archivo >> nro)
		{
			getline(archivo, nombre);
			nombre.erase(nombre.begin()); // borra el espacio en blanco
			g.calles[nombre] = nro;
			g.ncalles++;
		}
		archivo.close();
	}
	
	else cerr << "ERROR: No se pudo abrir 'calles.txt'" << endl;
}

/**
* Con motivo de prueba,
* imprime las calles 
* leÃ­das de 'calles.txt'
*/
void imprimirCalles()
{
	map<string,int>::iterator it = g.calles.begin();
	
	while (it != g.calles.end()) cout << it->second << " : " << (it++)->first << endl;
}

void read(){
	
	leerVertices(); //lee los vertices del archivo
	
	inicializarMatrizMotoqueros();
	inicializarMatrizRollistas();
	
	leerSegmentos();
	
}

/**
* Lee los vÃ©rtices de 'vertices.txt'
* y los carga en el vector vertices.
*/
void leerVertices()
{
	ifstream archivo ("vertices.txt");
	
	int int_c, int_a;
	int nro, i;
	string buffer, str_c, str_a;
	g.nvertices = 0;
	
	g.vertices.clear();
	g.vertices.resize(VERTICES_MAX);
	
	if (archivo.is_open())
	{
		while (archivo.good() && archivo >> nro)
		{
			getline(archivo, buffer);
			Vertice v;
			
			i = 1;
			while (1)
			{
				while (buffer[i] != ' ') 
				{
					str_c.push_back(buffer[i]);
					i++;
				}
				//int_c = stoi(str_c); // string->int : agregar bandera -std=c++11
				
				istringstream bufferC(str_c);
				
				bufferC >> int_c;
				v.calle.push_back(int_c);
				
				i++;
				while (buffer[i] != ' ' && buffer[i] != '\0') 
				{
					str_a.push_back(buffer[i]);
					i++;
				}
				
				//int_a = stoi(str_a); // string->int : agregar bandera -std=c++11
				
				istringstream bufferA(str_a);
				
				bufferA >> int_a;
				v.altura.push_back(int_a);
				
				str_c.clear();
				str_a.clear();
				
				if (buffer[i] == '\0') break;
				else i++;
			}
			
			g.vertices[nro] = v;
			g.verticesUsados.push_back(nro);
			g.nvertices++;
		}
		
		archivo.close(); 
	}
	
	else cerr << "ERROR: No se pudo abrir 'vertices.txt'." << endl;
}

void imprimirVertices()
{
	int i = 0;
	int f = g.vertices.size();
	
	vector<int>::iterator it1;
	vector<int>::iterator it2;
	for ( ; i < f ; i++)
	{
		it1 = g.vertices[i].calle.begin();
		it2 = g.vertices[i].altura.begin();
		
		cout << i << endl;
		
		while (it1 != g.vertices[i].calle.end())
			cout << *(it1++) << " " << *(it2++) << endl;
	}
}

/**
* Lee los arcos del grafo desde
* el archivo 'segmentos.txt' y
* los carga.
*/
void leerSegmentos()
{
	ifstream archivo ("segmentos.txt");
	
	int x, y;
	bool b_doble = false;
	vector<Segmento>::iterator it;
	
	g.segmentos.clear();
	g.segmentos.resize(g.vertices.size()+1);
	g.nsegmentos_unicos = 0;
	g.nsegmentos_dobles = 0;
	
	if (archivo.is_open())
	{
		while (archivo.good() && archivo >> x >> y) 
		{
			Segmento sreal;
			
			sreal.v = y;
			sreal.weight = 1;
			g.segmentos[x].push_back(sreal);                        
			
			g.infoAdy[x][y].distancia = 1;
			
			it = g.segmentos[y].begin();
			while (it != g.segmentos[y].end())
			{
				if (it->v == x)
				{
					b_doble = true;
					break;
				}
				it++;
			}
			
			if (b_doble)
			{
				g.nsegmentos_dobles++;
				g.nsegmentos_unicos--;
				b_doble = false;
			}
			
			else
				{                                       
					g.nsegmentos_unicos++;
				}
		}          
		
		archivo.close();
	}
	
	else cerr << "ERROR: No se pudo abrir el archivo 'segmentos.txt'." << endl;
}


/**
* Lee la tanda de pedidos
* del archivo 'pedidos.txt' y
* los carga en pedidos.
*/

void leerPedidos(){
	
	ifstream archivo ("pedidos.txt");
	
	int altura;
	string nombre, linea, numero;
	
	if (archivo.is_open())
	{
		pizzeria.pedidos.clear(); //ver si es necesario
		while (archivo.good() && getline(archivo, linea))
		{
			
			string aux_cadena(linea.begin(), linea.end());
			reverse(aux_cadena.begin(), aux_cadena.end());
			
			unsigned pos =  aux_cadena.find(" ");
			numero = aux_cadena.substr(0, pos);
			nombre = aux_cadena.substr(pos+1);
			
			reverse(numero.begin(), numero.end());
			reverse(nombre.begin(), nombre.end());
			
			
			//      altura = stoi(numero);
			
			istringstream bufferAl(numero);
			
			bufferAl >> altura;
			Direccion pedido;
			pedido.altura = altura;
			pedido.calle = nombre;
			
			pizzeria.pedidos.push_back(pedido);
		}
		
		archivo.close();
	}
	
	else cerr << "ERROR: No se pudo abrir 'pedidos.txt'" << endl;
}

/**
* Lee la ubicacion de la pizzeria
*/

void leerUbicacionPizzeria(){
	
	ifstream archivo ("pizzeria.txt");
	
	int altura;
	string nombre, linea, numero;
	
	
	if (archivo.is_open())
	{
		
		if (archivo.good() && getline(archivo, linea))
		{
			
			string aux_cadena(linea.begin(), linea.end());
			reverse(aux_cadena.begin(), aux_cadena.end());
			
			
			unsigned pos =  aux_cadena.find(" ");
			numero = aux_cadena.substr(0, pos);
			nombre = aux_cadena.substr(pos+1);
			
			reverse(numero.begin(), numero.end());
			reverse(nombre.begin(), nombre.end());
			
			//      altura = stoi(numero);
			
			istringstream bufferAl(numero);
			
			bufferAl >> altura;
			
			Direccion direccion;
			direccion.altura = altura;
			direccion.calle = nombre;
			
			pizzeria.dir = direccion;
			pizzeria.verticePizzeria = obtenerEsquina(direccion, false);
		}
		
		archivo.close();
	}
	
	else cerr << "ERROR: No se pudo abrir 'pedidos.txt'" << endl;
}

/**
* Lee pedidos VIP por stdin y los procesa
* hasta que salen del programa.
*/
void leerPedidosVIP()
{
	cout << ":: PEDIDOS VIP ::" << endl;
	cout << "Ingrese los pedidos VIP. Para finalizar escriba 'exit'." << endl;
	
	string entrada, nombre, numero;
	int altura;
	
	cin.ignore();
	
	while (getline(cin, entrada) && entrada != "exit")
	{
		
		string aux_cadena(entrada.begin(), entrada.end());
		reverse(aux_cadena.begin(), aux_cadena.end());
		
		
		unsigned pos =  aux_cadena.find(" ");
		numero = aux_cadena.substr(0, pos);
		nombre = aux_cadena.substr(pos+1);
		
		reverse(numero.begin(), numero.end());
		reverse(nombre.begin(), nombre.end());
		
		//      altura = stoi(numero);
		
		istringstream bufferAl(numero);
		
		bufferAl >> altura;
		
		Direccion pedido;
		pedido.altura = altura;
		pedido.calle = nombre;
		
		int* repartidorAsignado;
		repartidorAsignado = procesarPedidoVIP(pedido);
		
	}
	
	liberarRepartidores();
}

/** pone a todos los repartidores en estado: disponible = true**/

void liberarRepartidores(){

	for(int i=0; i<pizzeria.repartidoresR.size(); i++)
		pizzeria.repartidoresR[i].disponible = true;
	
	for(int i=0; i<pizzeria.repartidoresM.size(); i++)
		pizzeria.repartidoresM[i].disponible = true;
}


/**
*Retorna true si el grafo tiene vertices aislados y false si no 
al realizar el recorrido en bfs no tiene en cuenta el vertice eliminado, pasado como parametro
**/
bool bfs(int start, int borrado)
{
	queue<int> cola;
	g.processed.clear();
	g.discovered.clear();
	g.parents.clear();
	
	g.processed.assign(VERTICES_MAX, false);
	g.discovered.assign(VERTICES_MAX, false);
	g.parents.assign(VERTICES_MAX, -1);
	
	cola.push(start);               
	g.discovered[start] = true;             
	
	while (!cola.empty()) 
		
	{                    
		int actual = cola.front();      
		cola.pop();
		g.processed[actual] = true; 
		
		for (unsigned i = 0 ; i < g.segmentos[actual].size() ; i++) 
		{
			if ( g.segmentos[actual][i].v != borrado )
			{
				if (!g.discovered[g.segmentos[actual][i].v]) 
				{
					cola.push(g.segmentos[actual][i].v);
					g.discovered[g.segmentos[actual][i].v] = true;
					g.parents[g.segmentos[actual][i].v] = actual;
				}
			}
		}
	}
	
	int i =0;
	bool aislado =false;
	while(!aislado && i<g.verticesUsados.size()){
		
		if(g.discovered[g.verticesUsados[i]] == false)
			aislado = true;
		i++;
	}
	
	return aislado;
}

int sumaFloyd(int x, int y){
	if(x == INFINITY || y == INFINITY)
		return INFINITY;
	else
		return x+y;
}

void calcularDistanciasMotoqueros() {
	unsigned subK, subJ, subI;
	subK =0;
	int k = g.verticesUsados[subK];
	
	while(subK < g.verticesUsados.size()){
		subI =0;
		int i = g.verticesUsados[subI];
		
		while(subI < g.verticesUsados.size()){
			subJ =0;
			int j = g.verticesUsados[subJ];
			
			while(subJ < g.verticesUsados.size()){
				int x,y;
				x = g.infoAdy[i][k].distancia;
				y = g.infoAdy[k][j].distancia;
				int sum = sumaFloyd(x, y);
				if( g.infoAdy[i][j].distancia >  sum){
					g.infoAdy[i][j].distancia = sum;
					g.infoAdy[i][j].padre = g.infoAdy[k][j].padre;
				}
				subJ++;
				j  = g.verticesUsados[subJ];
			}
			subI++;
			i  = g.verticesUsados[subI];
		}
		subK++;
		k  = g.verticesUsados[subK];
	}
}

void calcularDistanciasRollistas() {
	int dist;    // distancia a traves del vertice k 
	int subK, subJ, subI;
	subK =0;
	sort(g.verticesEnRadio.begin(),g.verticesEnRadio.end());
	
	int k = g.verticesEnRadio[subK];
	
	while(subK < g.verticesEnRadio.size()){
		subI =0;
		int i = g.verticesEnRadio[subI];
		
		while(subI < g.verticesEnRadio.size()){
			subJ =0;
			int j = g.verticesEnRadio[subJ];
			
			while(subJ < g.verticesEnRadio.size()){
				int x,y;
				x = g.infoAdyRollista[i][k].distancia;
				y = g.infoAdyRollista[k][j].distancia;
				int sum = sumaFloyd(x, y);
				if( g.infoAdyRollista[i][j].distancia >  sum){
					g.infoAdyRollista[i][j].distancia = sum;
					g.infoAdyRollista[i][j].padre = g.infoAdyRollista[k][j].padre;
				}
				subJ++;
				j  = g.verticesEnRadio[subJ];
			}
			subI++;
			i  = g.verticesEnRadio[subI];
		}
		subK++;
		k  = g.verticesEnRadio[subK];
	}       
}

int siguienteVertice(int v){
	v++;
	
	while(v < g.verticesUsados.size()){
		if(g.verticesUsados[v] == true)
			return v;
		v++;
	}
}

void crearRepartidores(){
	
	
	pizzeria.repartidoresM.clear();
	pizzeria.repartidoresR.clear();
	//crea repartidores motoqueros
	for(int i =0; i< CANT_MOTOQUEROS; i++){
		
		Repartidor repartidor;
		
		
		repartidor.cantidadCuadras =0;
		repartidor.disponible = true;
		repartidor.recorridos = vector< vector <int> >();
		repartidor.historialPedidos.clear();
		pizzeria.repartidoresM.push_back(repartidor);
	}
	
	//crea repartidores rollistas
	for(int i =0; i< CANT_ROLLISTAS; i++){
		
		Repartidor repartidor;
		
		
		repartidor.cantidadCuadras =0;
		repartidor.disponible = true;
		repartidor.recorridos = vector< vector <int> >();
		repartidor.historialPedidos.clear();
		pizzeria.repartidoresR.push_back(repartidor);
	}
}


/**
* Obtiene la esquina mas cercana al lugar donde se tiene que entregar el pedido
* Esta esquina es la que se va a utilizar luego en los algoritmos para obtener el camino mÃ­nimo
**/

int obtenerEsquina(Direccion pedido, bool dirigido){
	
	string calle = pedido.calle;
	
	int n_calle = g.calles[calle];
	int altura = pedido.altura;
	
	int v1, v2;
	
	bool encontrado = false;
	int i =0;
	
	int a1 = 150;
	int a2 = -150;
	
	while(!encontrado && i < g.vertices.size()){
		int j=0;
		while(j < g.vertices[i].calle.size()){
			if(g.vertices[i].calle[j] == n_calle){
				int aux = altura - g.vertices[i].altura[j];
				if(aux <= a1 && aux >= 0){
					a1 = aux;
					v1 = i;
				}
				if(aux >= a2 && aux < 0){
					a2 = aux;
					v2 = i;
				}
				if(a1 < 150 && a2 > -150) //significa que se encontraron las esquinas mas proximas al punto de entrega
					encontrado = true;
			}
			j++;
		}
		i++;
	}
	
	if(encontrado){
		if(dirigido){ //al ser dirigido retorno el vertice anterior al lugar del pedido dependiendo del sentido
			
			vector<Segmento> temp;
			temp = g.segmentos[v1];
			int k =0;
			while(k < temp.size())
			{
				if(g.segmentos[v1][k].v == v2){
					return v1;
				}
				k++;
			}
			temp = g.segmentos[v2];
			k =0;
			while(k < temp.size())
			{
				if(g.segmentos[v2][k].v == v1){
					return v2;
				}
				k++;
			}
			
		}
		else{ //si no es dirigido, retorno el vertice mas cerca al lugar del pedido
			
			if(altura - a1 > altura + a2)
				return v1;
			else
				return v2;
		}
	}
}

bool pertenece(vector<int> &vec, int elem){
	
	int i =0;
	while(i < vec.size()){
		if(vec[i] == elem)
			return true;
		
		i++;
	}
	
	return false;
	
}

/**
* Procesa los pedidos que se encuentran en el vector pedidos, asignando a los repartidores los pedidos
**/

void procesarPedidos(){
	
	
	
	while(!pizzeria.pedidos.empty()){
		
		int v;
		Direccion dir;
		dir = direccionMasCercana(pizzeria.dir, pizzeria.pedidos, MATRIZ_ROLLISTAS); //retorna la direccion mas cercana, ordenando el vector, con el valor mas cercano al final
		
		v = obtenerEsquina(dir, false);
		
		procesarRollista(v, dir);
		
		while(hayMotoqueros() && !pizzeria.pedidos.empty()){
			//obtengo vertice mas lejano
			dir = direccionMasLejana(pizzeria.dir, pizzeria.pedidos, MATRIZ_MOTOQUEROS); //retorna la direccion mas lejana, ordenando el vector, con el valor mas cercano al final
			
			v = obtenerEsquina(dir, true);
			
			int motoquero;
			motoquero = obtenerMotoquero();
			
			if(motoquero != -1){
				
				vector<int> recorrido;
				vector<int> aux;
				int cant = 0;
				Direccion direccionActual = pizzeria.dir;
				int verticeActual = pizzeria.verticePizzeria;
				
				pizzeria.pedidos.erase(pizzeria.pedidos.begin(),pizzeria.pedidos.begin()+1); //borra el primer elemento (el mas lejano)
				
				aux = obtenerCamino(verticeActual,v, MATRIZ_MOTOQUEROS);
				if(!aux.empty())
					recorrido.insert(recorrido.end(),aux.begin(), aux.end());
				(pizzeria.repartidoresM[motoquero]).historialPedidos.push_back(dir);
				
				verticeActual = v;
				direccionActual = dir;
				
				dir = direccionMasCercana(direccionActual, pizzeria.pedidos, MATRIZ_MOTOQUEROS); //retorna la direccion mas cercana, ordenando el vector, con el valor mas cercano al final
				
				v = obtenerEsquina(dir, true);
				
				cant +2; // Â¿mas 2?
				while(cant < 7 && !pizzeria.pedidos.empty()){
					
					pizzeria.pedidos.pop_back();    
					
					aux = obtenerCamino(verticeActual,v, MATRIZ_MOTOQUEROS);
					if(!aux.empty())
						recorrido.insert(recorrido.end(),aux.begin(), aux.end());
					
					(pizzeria.repartidoresM[motoquero]).historialPedidos.push_back(dir);
					verticeActual = v;
					direccionActual = dir;
					if(!pizzeria.pedidos.empty()){
						dir = direccionMasCercana(direccionActual, pizzeria.pedidos, MATRIZ_MOTOQUEROS); //retorna la direccion mas cercana, ordenando el vector, con el valor mas cercano al final
						v = obtenerEsquina(dir, true);
					}
					
					cant++;
				}
				
				aux = obtenerCamino(verticeActual,pizzeria.verticePizzeria, MATRIZ_MOTOQUEROS);
				if(!aux.empty())
					recorrido.insert(recorrido.end(),aux.begin(), aux.end());
				
				(pizzeria.repartidoresM[motoquero]).recorridos.push_back(recorrido);
				int c = recorrido.size() - 1; //cantidad de cuadras en el recorrido (cantidad de vertices - 1)
				(pizzeria.repartidoresM[motoquero]).cantidadCuadras += c;
				pizzeria.repartidoresM[motoquero].disponible = false;
			}
		}
		
		if(!hayRollistas() && !hayMotoqueros())
			cout << "No hay repartidores libres para atender la solicitud!" << endl;
	}
	
	// pone en disponible a todos los repartidores
	
	liberarRepartidores();
	
}

/**
* Obtiene un pedido VIP y lo
* procesa
Retorna un arreglo, indicando el repartidor que fue asignado donde: la primera posicion obtiene el repartidorRollista y en la segunda posicion
el repartidorMotoquero, dejando un valor de -1 como no asignado
*/
int* procesarPedidoVIP(Direccion &pedido)
{
	
	int v;
	
	int repartidorAsignado[] = {-1, -1};
	
	v = obtenerEsquina(pedido, false);
	
	
	if(pertenece(g.verticesEnRadio, v) && hayRollistas()){
		
		int rollista;
		rollista = obtenerRollista();
		
		if(rollista != -1){
			
			vector<int> recorrido;
			int verticeActual = pizzeria.verticePizzeria;
			recorrido = obtenerCamino(verticeActual,v, MATRIZ_ROLLISTAS);
			
			(pizzeria.repartidoresR[rollista]).historialPedidos.push_back(pedido);
			verticeActual = v;
			
			
			vector<int> aux;
			aux = obtenerCamino(verticeActual,pizzeria.verticePizzeria, MATRIZ_ROLLISTAS);
			if(!aux.empty())
				recorrido.insert(recorrido.end(),aux.begin(), aux.end());
			
			(pizzeria.repartidoresR[rollista]).recorridos.push_back(recorrido);
			int c = recorrido.size() - 1; //cantidad de cuadras en el recorrido (cantidad de vertices - 1)
			(pizzeria.repartidoresR[rollista]).cantidadCuadras += c;
			pizzeria.repartidoresR[rollista].disponible = false;
			repartidorAsignado[0] = rollista;
			
			
			cout << "Informe entrega VIP con Destino: " << pedido.calle << " " << pedido.altura << endl;
			cout << "Repartidor asignado: Rollista N: " << rollista << endl;
			cout << "Recorrido: " << endl;
			mostrarRecorrido(recorrido);
			cout << "Cantidad de cuadras: " << c << endl;
			
		}
		
	}
	else if(hayMotoqueros()){
		int motoquero;
		motoquero = obtenerMotoquero();
		
		if(motoquero != -1){
			
			
			v = obtenerEsquina(pedido, true);
			
			vector<int> recorrido;
			int verticeActual = pizzeria.verticePizzeria;
			recorrido = obtenerCamino(verticeActual,v, MATRIZ_MOTOQUEROS);
			
			(pizzeria.repartidoresM[motoquero]).historialPedidos.push_back(pedido);
			verticeActual = v;
			
			
			vector<int> aux;
			aux = obtenerCamino(verticeActual,pizzeria.verticePizzeria, MATRIZ_MOTOQUEROS);
			if(!aux.empty())
				recorrido.insert(recorrido.end(),aux.begin(), aux.end());
			
			(pizzeria.repartidoresM[motoquero]).recorridos.push_back(recorrido);
			int c = recorrido.size() - 1; //cantidad de cuadras en el recorrido (cantidad de vertices - 1)
			(pizzeria.repartidoresM[motoquero]).cantidadCuadras += c;
			pizzeria.repartidoresM[motoquero].disponible = false;
			repartidorAsignado[1] = motoquero;
			
			
			cout << "Informe entrega VIP con Destino: " << pedido.calle << " " << pedido.altura << endl;
			cout << "Repartidor asignado: Motoquero N: " << motoquero << endl;
			cout << "Recorrido: " << endl;
			mostrarRecorrido(recorrido);
			cout << "Cantidad de cuadras: " << c << endl;
			
		}
	}
	else {
		cout << "No hay repartidores libres para atender la solicitud!" << endl;
	}
	
	return repartidorAsignado;
}

/**
*Funcion que compara las distancias de las direcciones con respecto a la pizzeria, retorna true si d1 esta mas lejos que d2
**/
bool compararDireccionesR(Direccion d1, Direccion d2){
	int v1,v2,dist1, dist2;
	
	v1 = obtenerEsquina(d1, false);
	v2 = obtenerEsquina(d2, false);
	dist1 = obtenerDistanciaR(pizzeria.verticePizzeria, v1);
	dist2 = obtenerDistanciaR(pizzeria.verticePizzeria, v2);
	
	return (dist1 > dist2); 
}


bool compararDireccionesM(Direccion d1, Direccion d2){
	int v1,v2,dist1, dist2;
	
	v1 = obtenerEsquina(d1, true);
	v2 = obtenerEsquina(d2, true);

	dist1 = obtenerDistanciaM(pizzeria.verticePizzeria, v1);
	dist2 = obtenerDistanciaM(pizzeria.verticePizzeria, v2);
	
	return (dist1 > dist2); 
}

vector<int> obtenerCamino(int v1, int v2, int m){
	
	int vi;
	stack<int> pila;
	
	vector<int> camino;
	
	if(v1 != v2){
		switch(m){
		case MATRIZ_MOTOQUEROS:
			
			pila.push(v2);
			vi = g.infoAdy[v1][v2].padre;
			
			while( vi != v1){
				pila.push(vi);
				vi = g.infoAdy[v1][vi].padre;
				
			}
			
			camino.push_back(v1);
			
			while(!pila.empty()){
				camino.push_back(pila.top());
				pila.pop();
			}
			break;
		case MATRIZ_ROLLISTAS:
			
			if(pertenece(g.verticesEnRadio,v1) && pertenece(g.verticesEnRadio,v2)){
				pila.push(v2);
				vi = g.infoAdyRollista[v1][v2].padre;
				
				
				while( vi != v1){
					pila.push(vi);
					vi = g.infoAdyRollista[v1][vi].padre;
					
				}
				
				camino.push_back(v1);
				
				while(!pila.empty()){
					camino.push_back(pila.top());
					pila.pop();
				}
			}
			
			break;
		}
	}
	
	return camino;
}

int obtenerDistanciaM(int v1, int v2){
	return g.infoAdy[v1][v2].distancia;
}


int obtenerDistanciaR(int v1, int v2){
	return g.infoAdyRollista[v1][v2].distancia;
	
}
/**
*       Marca los segmentos que esten en el RADIO_ROLLISTAS como dobles
*       y marca al vector como enRadio
**/
void verticesRadio(int centro){
	
	vector< queue<int> > vertices;
	
	vertices.resize(RADIO_ROLLISTAS+1);
	int dist = 0;
	vertices[dist].push(centro);
	g.verticesEnRadio.push_back(centro);
	
	
	while(dist < RADIO_ROLLISTAS){
		
		while(!vertices[dist].empty()){
			
			int verticeActual;
			verticeActual = vertices[dist].front();
			vertices[dist].pop();

			int i =0;
			while(i < g.segmentos[verticeActual].size()){
				int v;
				v = g.segmentos[verticeActual][i].v;
				
				g.infoAdyRollista[verticeActual][v].distancia = 1;
				g.infoAdyRollista[v][verticeActual].distancia = 1;
				if(!pertenece(g.verticesEnRadio, v)){
					g.verticesEnRadio.push_back(v);
					
					vertices[dist+1].push(v);
				}
				i++;
			}
			
			int subI =0;
			int cont =0; //contador de vertices, a lo sumo van a ser 3 (vertices que tienen como padre al vertice verticeActual)
			
			while(cont < 3 && subI < g.verticesUsados.size()){
				
				int v = g.verticesUsados[subI];
				if(g.infoAdy[v][verticeActual].distancia == 1){
					if(!pertenece(g.verticesEnRadio,v)){
						
						g.infoAdyRollista[verticeActual][v].distancia = 1;
						g.infoAdyRollista[v][verticeActual].distancia = 1;
						
						vertices[dist+1].push(v);
						
						g.verticesEnRadio.push_back(v);
					}
					cont++;
				}
				subI++;
			}
		}
		dist++;
	}
	
}

bool hayRollistas(){
	
	vector<Repartidor>::iterator it = pizzeria.repartidoresR.begin();
	while (it != pizzeria.repartidoresR.end())
		if ((it++)->disponible == true) return true;
	
	return false;
}

bool hayMotoqueros(){
	vector<Repartidor>::iterator it = pizzeria.repartidoresM.begin();
	while (it != pizzeria.repartidoresM.end())
		if ((it++)->disponible == true) return true;
	
	return false;
}

Direccion direccionMasCercana(Direccion d, vector<Direccion> &ds, int m){
	
	switch(m){
	case MATRIZ_ROLLISTAS:
		sort(ds.begin(), ds.end(),compararDireccionesR);
		break;
		
	case MATRIZ_MOTOQUEROS:
		sort(ds.begin(), ds.end(),compararDireccionesM);        
		break;
	}
	
	return ds.back();
}

Direccion direccionMasLejana(Direccion d, vector<Direccion> &ds, int m){
	switch(m){
	case MATRIZ_ROLLISTAS:
		sort(ds.begin(), ds.end(),compararDireccionesR);
		break;
		
	case MATRIZ_MOTOQUEROS:
		sort(ds.begin(), ds.end(),compararDireccionesM);        
		break;
	}
	
	return ds.front();
}

int obtenerRollista(){
	
	if(hayRollistas()){
		
		int i =0;
		while(i < pizzeria.repartidoresR.size()){
			
			if(pizzeria.repartidoresR[i].disponible)
				return i;
			i++;
		}
	}
	return -1;
}

int obtenerMotoquero(){
	if(hayMotoqueros()){
		int i =0;
		while(i < pizzeria.repartidoresM.size()){
			
			if(pizzeria.repartidoresM[i].disponible)
				return i;
			i++;
		}
	}
	return -1;
}
void inicializarMatrizMotoqueros(){
	g.infoAdy.resize(VERTICES_MAX);         
	
	for(int i = 0; i < VERTICES_MAX; i++){
		
		g.infoAdy[i].resize(VERTICES_MAX);              
		for(int j =0; j< VERTICES_MAX; j++){
			
			InfoAdyacencia inf;
			
			if(i == j)
				inf.distancia =0;
			else
				inf.distancia =INFINITY;
			
			inf.padre = i;
			g.infoAdy[i][j] = inf;
		}
	}
}

void procesarRollista(int v, Direccion dir){
	
	while(hayRollistas() && !pizzeria.pedidos.empty()){
		
		int rollista;
		rollista = obtenerRollista();
		
		if(rollista != -1){
			
			vector<int> recorrido;
			vector<int> aux;
			int cant = 0;
			Direccion direccionActual = pizzeria.dir;
			
			int verticeActual = pizzeria.verticePizzeria;
			
			while(pertenece(g.verticesEnRadio, v) && cant < 3 && !pizzeria.pedidos.empty()){
				
				pizzeria.pedidos.pop_back();    
				
				aux = obtenerCamino(verticeActual,v, MATRIZ_ROLLISTAS);
				
				if(!aux.empty())
					recorrido.insert(recorrido.end(),aux.begin(), aux.end()-1);
				
				(pizzeria.repartidoresR[rollista]).historialPedidos.push_back(dir);
				verticeActual = v;
				direccionActual = dir;
				
				if(!pizzeria.pedidos.empty()){
					dir = direccionMasCercana(direccionActual, pizzeria.pedidos, MATRIZ_ROLLISTAS); //retorna la direccion mas cercana, ordenando el vector, con el valor mas cercano al final
					v = obtenerEsquina(dir, false);
				}
				
				cant++;
			}
			
			aux = obtenerCamino(verticeActual,pizzeria.verticePizzeria, MATRIZ_ROLLISTAS);
			if(!aux.empty())
				recorrido.insert(recorrido.end(),aux.begin(), aux.end());
			
			(pizzeria.repartidoresR[rollista]).recorridos.push_back(recorrido);
			int c = recorrido.size() - 1; //cantidad de cuadras en el recorrido (cantidad de vertices - 1)
			(pizzeria.repartidoresR[rollista]).cantidadCuadras += c;
			pizzeria.repartidoresR[rollista].disponible = false;
		}
		
	}

}

void procesarPedidosMejora(){

	while(!pizzeria.pedidos.empty()){
		
		int v;
		Direccion dir;
		vector<int> verticesIncluidos;
		
		dir = direccionMasCercana(pizzeria.dir, pizzeria.pedidos, MATRIZ_ROLLISTAS); //retorna la direccion mas cercana, ordenando el vector, con el valor mas cercano al final
		
		v = obtenerEsquina(dir, false);
		
		procesarRollista(v, dir);
		
		while(hayMotoqueros() && !pizzeria.pedidos.empty()){
		
			int motoquero;
			motoquero = obtenerMotoquero();
			
			if(motoquero != -1){
				
				vector<int> recorrido;
				
				int cant = 0;
				Direccion direccionActual = pizzeria.dir;
				int verticeActual = pizzeria.verticePizzeria;
				Direccion direccionL = direccionMasLejana(pizzeria.dir, pizzeria.pedidos, MATRIZ_MOTOQUEROS); //retorna la direccion mas lejana, ordenando el vector, con el valor mas cercano al final
				
				v = obtenerEsquina(direccionL, true);
				
				
				int radio = obtenerDistanciaM(verticeActual, v);
				if(obtenerDistanciaM(v, verticeActual) > radio)
					radio = obtenerDistanciaM(v, verticeActual);
			
				verticesIncluidosEnRadios(verticeActual, v, radio, verticesIncluidos);
				
				vector<Direccion> direccionesIncluidas , direccionesRecorrido;
				
				
				for(int i=0; i< pizzeria.pedidos.size(); i++){
					
					Direccion dir;
					dir = pizzeria.pedidos[i];
					
					int esquina = obtenerEsquina(dir, true);
					
					if(pertenece(verticesIncluidos, esquina)){
						direccionesIncluidas.push_back(dir);
					}
					
				}
				
				
				if(direccionesIncluidas.size() <= CAPACIDAD_MOTOQUEROS)
					direccionesRecorrido = direccionesIncluidas;
				else {
					
					direccionesRecorrido.push_back(direccionL);
					int cant =1;
					while(cant < CAPACIDAD_MOTOQUEROS){
						Direccion d = direccionesIncluidas.back();
						direccionesRecorrido.push_back(d);
						
						direccionesIncluidas.pop_back();
						cant++;
					}
				}
				
				vector<int> verticesEntrega = obtenerVerticesEntrega(direccionesRecorrido);
				
				sort(direccionesRecorrido.begin(), direccionesRecorrido.end(), compararDireccionesM);
				
				for(int i = direccionesRecorrido.size()-1; i >= 0; i--){
					(pizzeria.repartidoresM[motoquero]).historialPedidos.push_back(direccionesRecorrido[i]);
					quitarDireccion(direccionesRecorrido[i], pizzeria.pedidos);
				}
				
				vector <int> aux;
				verticeActual = pizzeria.verticePizzeria;
				
				for(int i = verticesEntrega.size()-1; i >= 0; i--){
					
					
					
					if(verticeActual != verticesEntrega[i]){
						aux = obtenerCamino(verticeActual,verticesEntrega[i], MATRIZ_MOTOQUEROS);
						if(!aux.empty())
							recorrido.insert(recorrido.end(),aux.begin(), aux.end()-1);
					}
					verticeActual = verticesEntrega[i];
				}
				
				aux = obtenerCamino(verticeActual,pizzeria.verticePizzeria, MATRIZ_MOTOQUEROS);
				if(!aux.empty())
					recorrido.insert(recorrido.end(),aux.begin(), aux.end());
				
				(pizzeria.repartidoresM[motoquero]).recorridos.push_back(recorrido);
				int c = recorrido.size() - 1; //cantidad de cuadras en el recorrido (cantidad de vertices - 1)
				(pizzeria.repartidoresM[motoquero]).cantidadCuadras += c;
				pizzeria.repartidoresM[motoquero].disponible = false;
				
				verticesIncluidos.clear();
				direccionesRecorrido.clear();
				
			}
		}
		if(!hayRollistas() && !hayMotoqueros())
			cout << "No hay repartidores libres para atender la solicitud!" << endl;
	}
	
	// pone en disponible a todos los repartidores
	
	liberarRepartidores();
	
}

void inicializarMatrizRollistas(){
	g.infoAdyRollista.resize(VERTICES_MAX);         
	
	for(int i = 0; i < VERTICES_MAX; i++){
		
		g.infoAdyRollista[i].resize(VERTICES_MAX);              
		for(int j =0; j< VERTICES_MAX; j++){
			
			InfoAdyacencia inf;
			
			if(i == j)
				inf.distancia =0;
			else
				inf.distancia =INFINITY;
			
			inf.padre = i;
			g.infoAdyRollista[i][j] = inf;
		}
	}
}

/**
*Almacena en el vector: verticesIncluidosEnRadios, los vertices que pertenecen a: S1 y S2
*donde S1: sector con centro: verticeActual y radio: radio
*donde S2: sector con centro: v y radio: radio
*este sector es donde se buscarÃ¡n los pedidos
**/
void verticesIncluidosEnRadios(int verticeActual, int v, int radio, vector<int> &verticesIncluidosEnRadios){
	
	
	for(int i=0; i<g.verticesUsados.size(); i++){
		int d1,d2;
		d1 = g.infoAdy[verticeActual][g.verticesUsados[i]].distancia;
		if(d1 <= radio){
			d2 = g.infoAdy[v][g.verticesUsados[i]].distancia;
			if(d2 <= radio)
				verticesIncluidosEnRadios.push_back(g.verticesUsados[i]);
		}
	}
	
}

/**
*Se eligen las direccionesIncluidas para repartir entre el verticeActual y el vertice v (inclusive)
* con el siguiente criterio:
*- si la cantidad de direcciones del vector son mayores a las que puede entregar el repartidor, 
*se toma la capacidad  a la mitad (1 para rollistas, 4 para motoqueros) y se busca esa
*cantidad mas cercana a cada vertice extremo. Luego se retornan las direcciones elegidas
*- si la cantidad es menor o igual, se retornan todas las direcciones
* todas las direcciones que se van a retornar, se eliminan del vector: pizzeria.pedidos
**/
vector<Direccion> elegirDirecciones(int verticeActual, int v, vector<Direccion> &direccionesIncluidas, int tipoRepartidor){
	
}


vector<int> obtenerVerticesEntrega(vector<Direccion> direccionesRecorrido){
	
	sort(direccionesRecorrido.begin(), direccionesRecorrido.end(), compararDireccionesM);
	
	
	vector<int> recorrido;
	int v = obtenerEsquina(direccionesRecorrido.back(), true);
	recorrido.push_back(v);
	direccionesRecorrido.pop_back();
	
	
	while(!direccionesRecorrido.empty()){
		Direccion proximo = direccionesRecorrido.back();
		v = obtenerEsquina(direccionesRecorrido.back(), true);
		int dist = obtenerDistanciaM(recorrido.back(), v);
		
		for(int i=0; i< direccionesRecorrido.size()-1; i++){
			
			v = obtenerEsquina(direccionesRecorrido[i], true);
			int d = obtenerDistanciaM(recorrido.back(),v);
			
			if(d < dist){
				dist = d;
				proximo = direccionesRecorrido[i];
			}
		}
		
		//direccionesRecorrido.erase(find(direccionesRecorrido.begin(), direccionesRecorrido.end(), proximo));
		quitarDireccion(proximo, direccionesRecorrido);
		
		
		recorrido.push_back(obtenerEsquina(proximo,true));
	}
	return recorrido;
}

void quitarDireccion(Direccion d, vector<Direccion> & direcciones){
	
	bool quitado = false;
	int i =0;
	
	vector<Direccion>::iterator it = direcciones.begin();
	while(!quitado && it != direcciones.end()){
		
		if(it->calle== d.calle && it->altura == d.altura){
			direcciones.erase(it);
			quitado = true;
		}
		
		it++;
	}
	
	
	
}


void resetearContadores()
{
	int i;
	
	for (i = 0 ; i < pizzeria.repartidoresR.size() ; i++)
		pizzeria.repartidoresR[i].cantidadCuadras = 0;
	
	for (i = 0 ; i < pizzeria.repartidoresM.size() ; i++)
		pizzeria.repartidoresM[i].cantidadCuadras = 0;
}

void mostrarRecorrido(vector<int> recorrido){
	int k = 0;
	for(k=0; k< recorrido.size()-1; k++){
		cout << recorrido[k] << " -> "; 
	}
	cout << recorrido[k] << endl;
}

void mostrarInforme(int &totalDeCuadras){
	
	int contador_aux = 0;
	totalDeCuadras = 0;
	
	cout << "---------- INFORME ----------" << endl << endl;
	cout << " INFORMACION DE ROLLISTAS:" << endl;
	
	for(int i =0; i<pizzeria.repartidoresR.size(); i++){
		
		cout << endl << " ROLLISTA: " << i+1 << endl;
		vector<Direccion> domiciliosP;
		domiciliosP = pizzeria.repartidoresR[i].historialPedidos;
		
		sort(domiciliosP.begin(), domiciliosP.end(), compararDireccionesR); //ordena los pedidos de mayor a menor distancia
		
		
		cout << " DOMICILIOS DE ENTREGA: " << endl;
		for(int j=domiciliosP.size()-1; j >= 0; j--){
			cout << "  " << domiciliosP[j].calle << " " << domiciliosP[j].altura << endl;
		}
		
		cout << " RECORRIDOS: "<< endl;
		if(pizzeria.repartidoresR[i].recorridos.size() == 0){
			cout << "NO HAY RECORRIDOS PARA EL REPARTIDOR: " << i << endl;
		}
		else{
			for(int j=0; j<pizzeria.repartidoresR[i].recorridos.size(); j++){
				vector<int> recorrido = pizzeria.repartidoresR[i].recorridos[j];
				
				cout << " Recorrido: " << j << endl;
				cout << "  ";
				int k;
				for(k=0; k< recorrido.size()-1; k++){
					cout << recorrido[k] << " -> "; 
				}
				cout << recorrido[k] << endl;
				int c = recorrido.size() - 1;
				cout << "  CANTIDAD DE CUADRAS EN EL RECORRIDO: " << c << endl;
			}
		}
		int cant = pizzeria.repartidoresR[i].cantidadCuadras;
		cout << "  CANTIDAD DE CUADRAS DE TODOS LOS RECORRIDOS: " << cant  << endl;
		contador_aux +=  cant;
	}
	
	
	cout << "  TOTAL DE CUADRAS RECORRIDAS POR ROLLISTAS: " << contador_aux  << endl;
	
	totalDeCuadras += contador_aux;
	contador_aux = 0;
	
	
	cout << " INFORMACION DE MOTOQUEROS:" << endl;
	
	for(int i =0; i<pizzeria.repartidoresM.size(); i++){
		
		cout << endl << " MOTOQUERO: " << i+1 << endl;
		vector<Direccion> domiciliosP;
		domiciliosP = pizzeria.repartidoresM[i].historialPedidos;
		
		sort(domiciliosP.begin(), domiciliosP.end(), compararDireccionesR); //ordena los pedidos de mayor a menor distancia
		
		cout << " DOMICILIOS DE ENTREGA: " << endl;
		for(int j=domiciliosP.size()-1; j >= 0; j--){
			cout << "  " << domiciliosP[j].calle << " " << domiciliosP[j].altura << endl;
		}
		
		cout << " RECORRIDOS: "<< endl;
		
		if(pizzeria.repartidoresM[i].recorridos.size() == 0){
			cout << "NO HAY RECORRIDOS PARA EL REPARTIDOR: " << i << endl;
		}
		else{
			
			for(int j=0; j<pizzeria.repartidoresM[i].recorridos.size(); j++){
				vector<int> recorrido = pizzeria.repartidoresM[i].recorridos[j];
				
				
				cout << " Recorrido: " << j << endl;
				cout << "  ";
				int k;
				for(k=0; k< recorrido.size()-1; k++){
					cout << recorrido[k] << " -> "; 
				}
				cout << recorrido[k] << endl;
				
				
				int c = recorrido.size() - 1;
				cout << "  CANTIDAD DE CUADRAS EN EL RECORRIDO: " << c << endl;
			}
		}
		int cant = pizzeria.repartidoresM[i].cantidadCuadras;
		cout << "  CANTIDAD DE CUADRAS DE TODOS LOS RECORRIDOS: " << cant  << endl;
		contador_aux +=  cant;
	}
	
	
	totalDeCuadras += contador_aux;
	cout << "  TOTAL DE CUADRAS RECORRIDAS POR MOTOQUEROS: " << contador_aux  << endl;
}

void mostrarInformeFinal()
{
	float total = totalCuadrasEnunciado-totalCuadrasMejora;
	
	cout << ":: INFORME RESUMIDO FINAL ::" << endl;
	cout << "Total cuadras recorridas según enunciado: " << totalCuadrasEnunciado << endl;
	cout << "Total cuadras recorridas según mejora propuesta: " << totalCuadrasMejora << endl;
	
	if(totalCuadrasEnunciado != 0 && totalCuadrasMejora !=0){
	cout << "En base a la mejora, la diferencia absoluta es de " << total << " cuadras." << endl;
	cout << "Por lo tanto, para el caso propuesto";
	
	if (total < 0)
		cout << "no hubo mejora alguna, sino un empeoramiento del " << (total/totalCuadrasEnunciado)*100 << "%." << endl;
	else if (total==0)
		cout << "no hubo mejora alguna." << endl;
	else
		cout << "hubo una mejora del " << (total/totalCuadrasEnunciado)*100 << "%." << endl;
	}
}